#ifndef _SIMPLE_HASH_MAP__H_
#define _SIMPLE_HASH_MAP__H_

#include <memory>
#include <functional>
#include <utility>
#include <initializer_list>
#include <cstring>
#include <type_traits>

#include "vl_structure_exception.h"

namespace VL {

// 缺省 HashMap 尺寸
constexpr const size_t VL_DEFAULT_HASH_MAP_SIZE = 11;
// 缺省 HashMap 扩容因子
constexpr const float VL_DEFAULT_HASH_EXPAND_FACTOR = 0.75;
// 缺省 HashMap 扩容尺寸
constexpr const size_t VL_DEFAULT_HASH_EXPAND_SIZE = VL_DEFAULT_HASH_MAP_SIZE * VL_DEFAULT_HASH_EXPAND_FACTOR;

/**
 * @Author: CimZzz
 * @Date: 2023-06-09 10:52:09
 * 
 * 极简 Hash 表
 * 模板参数:
 * - KeyType: 键值类型
 * - ValueType: 值类型
 * - KeyHash: 键值哈希函数
 * 
 * 内部维护容器:
 * 
 * 1. 由 _ValueNode 组合而成的头尾链表
 * 2. _SimpleHashBucket(桶) 哈希数组, 每个数组元素是由 _HashNode 组合而成的双向链表
 */
template<class KeyType, class ValueType, class KeyHash = std::hash<KeyType> >
class SimpleHashMap {

private:
	template<typename Key, typename = void>
	struct _EqualCheck {
		typedef char yes[1];
		typedef char no[2];

		template<typename C, bool (C::*)(const C&) const>
		struct _checker {};

		template<typename C>
		static yes& test(_checker<C, &C::operator==>*);
		template<typename C>
		static no& test(...);
		static bool const value = sizeof(test<Key>(nullptr)) == sizeof(yes);
	};

	template<typename ...Ts>
	struct _make_void { typedef void type; };

	template<typename Key>
	struct _EqualCheck<Key, typename _make_void<decltype(std::declval<Key>() == std::declval<Key>())>::type>
		: public std::true_type {};

	// 值结点
	struct _ValueNode {
		_ValueNode(const KeyType& key, const ValueType& value, size_t hashCode): 
			front(nullptr), next(nullptr),
			hashCode(hashCode), key(key), value(value) {}
		_ValueNode* front;
		_ValueNode* next;
		size_t hashCode;
		KeyType key;
		ValueType value;
	};

	// 双链表结点
	struct _HashNode {
		_HashNode* next = nullptr;
		_ValueNode* valueNode = nullptr;
	};

	// 桶
	struct _SimpleHashBucket {
		_HashNode* linkedNode = nullptr;
		_HashNode* pendingNode = nullptr;
	};

	template<typename _KeyType, typename std::enable_if<_EqualCheck<_KeyType>::value, bool>::type = true>
	static bool _check_key_equal(const _ValueNode* node, const _KeyType& key, const size_t& hashCode) {
		return node->hashCode == hashCode && node->key == key;
	}

	template<typename _KeyType, typename std::enable_if<!_EqualCheck<_KeyType>::value, bool>::type = true>
	static bool _check_key_equal(const _ValueNode* node, const _KeyType& key, const size_t& hashCode) {
		return node->hashCode == hashCode;
	}

public:
	class iterator {
	public:
		struct iterator_ref {
			iterator_ref(const KeyType& key, ValueType& value): key(key), value(value), first(key), second(value) {}
			const KeyType& key;
			ValueType& value;
			const KeyType& first;
			ValueType& second;
		};
		~iterator() {
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
		}
	private:
		friend class SimpleHashMap;
		explicit iterator(_ValueNode* node): _node(node), _ref(nullptr) { }
		_ValueNode* _node;
		iterator_ref* _ref;
	public:
		bool operator==(const iterator& other) const {
			if(this->_node == nullptr || other._node == nullptr) {
				return this->_node == nullptr && other._node == nullptr;
			}
			return false;
		}
		bool operator!=(const iterator& other) const {
			return !this->operator==(other);
		}

		iterator& operator++() {
			if(this->_node == nullptr) {
				return *this;
			}
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
			this->_node = this->_node->next;
			return *this;
		}
		iterator& operator++(int) {
			if(this->_node == nullptr) {
				return *this;
			}
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
			this->_node = this->_node->next;
			return *this;
		}
		iterator_ref operator*() {
			return iterator_ref(this->_node->key, this->_node->value);
		}
		iterator_ref* operator->() {
			if(this->_ref == nullptr) {
				if(this->_node == nullptr) {
					return nullptr;
				}
				this->_ref = new iterator_ref(this->_node->key, this->_node->value);
			}
			return this->_ref;
		}
	};

	class const_iterator {
	public:
		struct const_iterator_ref {
			const_iterator_ref(const KeyType& key, const ValueType& value): key(key), value(value), first(key), second(value) {}
			const KeyType& key;
			const ValueType& value;
			const KeyType& first;
			const ValueType& second;
		};
		~const_iterator() {
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
		}
	private:
		friend class SimpleHashMap;
		explicit const_iterator(_ValueNode* node): _node(node), _ref(nullptr) { }
		_ValueNode* _node;
		const_iterator_ref* _ref;
	public:
		bool operator==(const const_iterator& other) const {
			if(this->_node == nullptr || other._node == nullptr) {
				return this->_node == nullptr && other._node == nullptr;
			}
			return false;
		}
		bool operator!=(const const_iterator& other) const {
			return !this->operator==(other);
		}

		const_iterator& operator++() {
			if(this->_node == nullptr) {
				return *this;
			}
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
			this->_node = this->_node->next;
			return *this;
		}
		const_iterator& operator++(int) {
			if(this->_node == nullptr) {
				return *this;
			}
			if(this->_ref != nullptr) {
				delete this->_ref;
				this->_ref = nullptr;
			}
			this->_node = this->_node->next;
			return *this;
		}
		const_iterator_ref operator*() {
			return const_iterator_ref(this->_node->key, this->_node->value);
		}
		const_iterator_ref* operator->() {
			if(this->_ref == nullptr) {
				if(this->_node == nullptr) {
					return nullptr;
				}
				this->_ref = new const_iterator_ref(this->_node->key, this->_node->value);
			}
			return const_iterator_ref(this->_node->key, this->_node->value);
		}
	};

public:
	virtual ~SimpleHashMap() {
		this->clear();
		free(this->buckets);
		this->buckets = nullptr;
	}
	explicit SimpleHashMap(): 
		buckets(nullptr),  _headNode(nullptr), _tailNode(nullptr), _size(0), 
		_bucketSize(VL_DEFAULT_HASH_MAP_SIZE), _expandSize(VL_DEFAULT_HASH_EXPAND_SIZE) {
	}

	SimpleHashMap(const std::initializer_list<std::pair<const KeyType, ValueType>>& initList): 
		buckets(nullptr), _headNode(nullptr), _tailNode(nullptr), _size(0), 
		_bucketSize(VL_DEFAULT_HASH_MAP_SIZE), _expandSize(VL_DEFAULT_HASH_EXPAND_SIZE) {
		this->_calc_new_cap(initList.size());
		for(auto iter : initList) {
			this->_emplace_not_expand(iter.first, iter.second);
		}
	}
	SimpleHashMap(const SimpleHashMap& map): 
		buckets(nullptr), _headNode(nullptr), _tailNode(nullptr), _size(0), 
		_bucketSize(VL_DEFAULT_HASH_MAP_SIZE), _expandSize(VL_DEFAULT_HASH_EXPAND_SIZE) {
		this->_calc_new_cap(map._size);
		for(auto iter : map) {
			this->_emplace_not_expand(iter.first, iter.second);
		}
	}

	SimpleHashMap(const SimpleHashMap&& map):
		buckets(map.buckets), _headNode(map._headNode), _tailNode(map._tailNode), _size(map._size), 
		_bucketSize(map._bucketSize), _expandSize(map._expandSize) {
		map.buckets = nullptr;
		map._headNode = nullptr;
		map._tailNode = nullptr;
		map._size = 0;
		map._bucketSize = VL_DEFAULT_HASH_MAP_SIZE;
		map._expandSize = VL_DEFAULT_HASH_EXPAND_SIZE;
	}

	const SimpleHashMap& operator =(const SimpleHashMap& map) {
		this->clear();
		this->_calc_new_cap(map._size);
		for(auto iter : map) {
			this->_emplace_not_expand(iter.first, iter.second);
		}
		return *this;
	}

	const SimpleHashMap& operator =(const SimpleHashMap&& map) {
		this->clear();
		this->buckets = map.buckets;
		this->_headNode = map._headNode;
		this->_tailNode = map._tailNode;
		this->_size = map._size;
		this->_bucketSize = map._bucketSize;
		this->_expandSize = map._expandSize;
		map.buckets = nullptr;
		map._headNode = nullptr;
		map._tailNode = nullptr;
		map._size = 0;
		map._bucketSize = VL_DEFAULT_HASH_MAP_SIZE;
		map._expandSize = VL_DEFAULT_HASH_EXPAND_SIZE;
	}

	iterator find(const KeyType& key) const {
		if(this->_size > 0) {
			size_t hashCode = this->hasher(key);
			size_t hashIdx = hashCode % this->_bucketSize;

			_SimpleHashBucket& bucket = this->buckets[hashIdx];
			if(bucket.linkedNode != nullptr) {
				_HashNode* existNode = bucket.linkedNode;
				while(existNode != nullptr) {
					_ValueNode* valueNode = existNode->valueNode;
					if(_check_key_equal(valueNode, key, hashCode)) {
						return iterator(valueNode);
					}
					existNode = existNode->next;
				}
			}
		}
		return this->end();
	}

	iterator emplace(const KeyType& key, const ValueType& value) {
		this->_calc_new_cap(1);
		return iterator(this->_emplace_not_expand(key, value));
	}

	void emplace(const std::initializer_list<std::pair<KeyType, ValueType>>& initList) {
		this->_calc_new_cap(initList.size());
		for(auto iter : initList) {
			this->_emplace_not_expand(iter.first, iter.value);
		}
	}

	// 回收资源
	void clear() {
		// 回收桶数组, 需要遍历每个桶回收链表结点
		if(this->buckets != nullptr) {
			for(size_t i = 0 ; i < this->_bucketSize ; i ++) {
				_SimpleHashBucket& bucket = this->buckets[i];
				if(bucket.pendingNode != nullptr) {
					_HashNode* tmpNode = bucket.pendingNode;
					_HashNode* nextNode = nullptr;
					while(tmpNode != nullptr) {
						nextNode = tmpNode->next;
						free(tmpNode);
						tmpNode = nextNode;
					}
				}
				bucket.linkedNode = nullptr;
				bucket.pendingNode = nullptr;
			}
		}
		// 回收
		if(this->_headNode != nullptr) {
			_ValueNode* tmpNode = this->_headNode;
			_ValueNode* nextNode = nullptr;
			while(tmpNode != nullptr) {
				nextNode = tmpNode->next;
				delete tmpNode;
				tmpNode = nextNode;
			}
			this->_headNode = nullptr;
			this->_tailNode = nullptr;
		}

		this->_size = 0;
	}

	// 获取尺寸
	size_t size() const {
		return this->_size;
	}

	iterator begin() const {
		return iterator(this->_headNode);
	}

	iterator end() const {
		return iterator(nullptr);
	}

	const_iterator const_begin() const {
		return const_iterator(this->_headNode);
	}

	const_iterator const_end() const {
		return const_iterator(nullptr);
	}
private:
	// 实际插入方法
	_ValueNode* _insert_new_value(
		_SimpleHashBucket& bucket,
		const KeyType& key,
		const ValueType& value,
		const size_t& hashCode
	) {
		_ValueNode* valueNode = new _ValueNode(key, value, hashCode);
		if(valueNode == nullptr) {
			throw VLStructureException("[simple hash map]: cannot alloc value node"); 
		}
		_HashNode* hashNode = (_HashNode *) malloc(sizeof(_HashNode));
		if(hashNode == nullptr) {
			free(valueNode);
			throw VLStructureException("[simple hash map]: cannot alloc hash node");
		}
		hashNode->next = nullptr;
		hashNode->valueNode = valueNode;
		if(bucket.linkedNode == nullptr) {
			bucket.linkedNode = hashNode;
		} else {
			hashNode->next = bucket.linkedNode;
			bucket.linkedNode = hashNode;
		}

		if(this->_headNode == nullptr) {
			this->_headNode = valueNode;
			this->_tailNode = valueNode;
		} else {
			this->_tailNode->next = valueNode;
			this->_tailNode = valueNode;
		}
		this->_size ++;
		return valueNode;
	}

	// 计算哈希, 决定插入或者替换元素
	_ValueNode* _emplace_not_expand(const KeyType& key, const ValueType& value) {
		size_t hashCode = this->hasher(key);
		size_t hashIdx = hashCode % this->_bucketSize;
		bool isInsert = true;

		_SimpleHashBucket& bucket = this->buckets[hashIdx];
		_ValueNode* valueNode = nullptr;
		if(bucket.linkedNode != nullptr) {
			_HashNode* existNode = bucket.linkedNode;
			while(existNode != nullptr) {
				valueNode = existNode->valueNode;
				if(_check_key_equal(valueNode, key, hashCode)) {
					valueNode->value = value;
					isInsert = false;
					break;
				}
				existNode = existNode->next;
			}
		}

		if(isInsert) {
			valueNode = this->_insert_new_value(bucket, key, value, hashCode);
		}

		return valueNode;
	}

	// 计算是否需要扩容, 如果返回值大于 0 表示需要扩容到
	void _calc_new_cap(size_t incCount) {
		size_t afterBucketSize = this->_bucketSize;
		size_t afterExpandSize = this->_expandSize;

		size_t afterItemSize = this->_size + incCount;
		while(afterItemSize > afterExpandSize) {
			// 每次尺寸乘 2
			afterBucketSize = afterBucketSize << 1;
			afterExpandSize = afterBucketSize * 0.75;
		}
		if(this->buckets == nullptr) {
			size_t mallocSize = sizeof(_SimpleHashBucket) * afterBucketSize;
			// 初始化桶数组
			this->buckets = (_SimpleHashBucket *)::malloc(mallocSize);
			if(this->buckets == nullptr) {
				// 开辟内存空间失败, 抛出异常
				throw VLStructureException("[simple hash map]: cannot alloc space, size: %lu", mallocSize);
			}
			// 填充 0
			::memset((void *)this->buckets, 0, mallocSize);

			this->_bucketSize = afterBucketSize;
			this->_expandSize = afterExpandSize;
		}

		if(this->_bucketSize != afterBucketSize) {
			size_t reallocSize = sizeof(_SimpleHashBucket) * afterBucketSize;
			// 扩容
			this->buckets = (_SimpleHashBucket *)::realloc((void *) this->buckets, reallocSize);
			if(this->buckets == nullptr) {
				// 扩容内存空间失败, 抛出异常
				throw VLStructureException("[simple hash map]: cannot realloc space, size: %lu", reallocSize);
			}
			// 填充 0
			::memset((void *)(this->buckets + this->_bucketSize), 0, sizeof(_SimpleHashBucket) * (afterBucketSize - this->_bucketSize));

			_HashNode* cacheHashNode = nullptr;
			// rehash
			for(size_t idx = 0 ; idx < this->_bucketSize ; idx ++) {
				_SimpleHashBucket& currentBucket = this->buckets[idx];
				cacheHashNode = currentBucket.linkedNode;
				currentBucket.linkedNode = currentBucket.pendingNode;
				currentBucket.pendingNode = nullptr;
				while(cacheHashNode != nullptr) {
					_HashNode* tempHashNode = cacheHashNode;
					cacheHashNode = cacheHashNode->next;
					_ValueNode* valueNode = tempHashNode->valueNode;
					// 计算哈希下标
					size_t hashIdx = valueNode->hashCode % afterBucketSize;
					_SimpleHashBucket& bucket = this->buckets[hashIdx];
					if(hashIdx <= idx || hashIdx >= this->_bucketSize) {
						// 添加到已处理的数组中
						tempHashNode->next = bucket.linkedNode;
						bucket.linkedNode = tempHashNode;
					} else {
						tempHashNode->next = bucket.pendingNode;
						bucket.pendingNode = tempHashNode;
					}
				}
			}

			this->_bucketSize = afterBucketSize;
			this->_expandSize = afterExpandSize;
		}
	}

private:

	// 桶
	_SimpleHashBucket* buckets;
	// 值链表头部
	_ValueNode* _headNode;
	// 值链表尾部
	_ValueNode* _tailNode;
	// 哈希工具
	KeyHash hasher;
	// 当前元素数量
	size_t _size;
	// 当前桶的数量
	size_t _bucketSize;
	// 扩容尺寸
	size_t _expandSize;
};

}

#endif // end _SIMPLE_HASH_MAP__H_